package org.example.everyday;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * <p>
 * Description:TODO 详细描述
 * <p>
 * Copyright: 天津联想协同科技有限公司
 * <p>
 *
 * @author anlu
 * @date 2022/4/27 14:45
 */
public class Lc417 {
    static int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};
    int[][] heights;
    int m,n;

    public static void main(String[] args) {
        Lc417 lc417 = new Lc417();

       int[][] heights = {{1,2,2,3,5},{3,2,3,4,4},{2,4,5,3,1},{6,7,1,4,5},{5,1,1,2,4}};
        //输出: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]
        List<List<Integer>> res = lc417.pacificAtlantic(heights);
        for (int i = 0; i < res.size(); i++) {
            List<Integer> list = res.get(i);
            System.out.println(list.toString());
        }
        System.out.println("输出完毕");

    }

    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        this.heights = heights;
        m = heights.length;
        n = heights[0].length;
        boolean[][] pacfic = new boolean[m][n];
        boolean[][] atlantic = new boolean[m][n];
        //遍历太平洋的行，列是0
        for(int i = 0; i < m; i++){
            dfs(i,0,pacfic);
        }
        //遍历太平洋的列
        for(int j = 0; j < n; j++){
            dfs(0,j,pacfic);
        }

        //遍历大西洋的行，列是0
        for (int i = 0; i < m; i++) {
            dfs(i,n - 1,atlantic);
        }
        //遍历大西洋的列，行是最后一行
        for (int i = 0; i < n - 1; i++) {
            dfs(m - 1,i,atlantic);
        }

        List<List<Integer>> res = new ArrayList<List<Integer>>();
        for(int i = 0; i < m; i++){
            for (int j = 0; j < n; j++) {
                if(pacfic[i][j] && atlantic[i][j]){
                    List<Integer> list  = new ArrayList<>();
                    list.add(i);
                    list.add(j);
                    res.add(list);
                }

            }
        }

        return res;
    }


    private void  dfs(int row,int col,boolean[][] ocean){
        if(ocean[row][col]){
            return;
        }
        ocean[row][col] = true;
        for (int[] dir:dirs){
            int newRow = row + dir[0],newCol = col + dir[1];
            if(newRow >=0 && newRow < m && newCol >= 0 && newCol < n && heights[newRow][newCol] >= heights[row][col]){
                dfs(newRow,newCol,ocean);
            }
        }
    }

}
